package com.gxc.tree;

import java.util.Deque;
import java.util.LinkedList;

/**
 *  从中序与后序遍历序列构造二叉树
 * 给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树
 */
public class BuildTree2 {

    public static void main(String[] args) {
        buildTree2(new int[]{15, 9, 10, 3, 20, 5, 7, 8, 4}, new int[]{15, 10, 9, 5, 4, 8, 7, 20, 3});
        System.out.println("---------");
    }

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return build(inorder, postorder, 0, inorder.length-1, 0 ,postorder.length-1);
    }

    private TreeNode build(int[] inorder, int[] postorder, int i, int j, int x, int y) {
        if (i>j) return null;

        int index = 0;
        for (; index < inorder.length; index++) {
            if (inorder[index] == postorder[y]) break;
        }

        int n = index - i;
        TreeNode node = new TreeNode(postorder[y]);
        node.left = build(inorder, postorder, i,  index-1, x, x + n-1);
        node.right = build(inorder, postorder, index+1,j, x+n, y-1);
        return node;
    }

    public static TreeNode buildTree2(int[] inorder, int[] postorder) {
        if (postorder == null || postorder.length == 0) {
            return null;
        }
        TreeNode root = new TreeNode(postorder[postorder.length - 1]);
        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        stack.push(root);
        int inorderIndex = inorder.length - 1;
        for (int i = postorder.length - 2; i >= 0; i--) {
            int postorderVal = postorder[i];
            TreeNode node = stack.peek();
            if (node.val != inorder[inorderIndex]) {
                node.right = new TreeNode(postorderVal);
                stack.push(node.right);
            } else {
                while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {
                    node = stack.pop();
                    inorderIndex--;
                }
                node.left = new TreeNode(postorderVal);
                stack.push(node.left);
            }
        }
        return root;
    }

}
